package main

import "fmt"

/*
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组 是数组中的一个连续部分。
*/
/*
思路：如果i位前面的最大子序为负数，是不是越加越小？还不如直接放弃，从自己算起呢！

动态规划表达式
	f(i)：代表从0到i位的最大子序和
动态规划方程：
	if f(i-1)>0
		f(i)=f(i-1)+nums[i] // 连上前面的数据
	else
		f(i)=nums[i] // 得了吧您内，放弃前面的数据，从自己开始吧
简化：
	f(i)=max{f(i-1),0} + nums[i]
	f(0)=nums[0]

返回结果：max{f[0]~f[n]}

*/
func maxSubArray1(nums []int) int {
	l := len(nums)
	f := make([]int, l)
	res := nums[0]
	for i := range nums {
		if i == 0 { // 初始化
			f[i] = nums[i]
			continue
		}

		f[i] = max(f[i-1], 0) + nums[i]
		res = max(res, f[i])

	}
	return res
}

/*
优化：

	f(i)=max{f(i-1),0} + nums[i]
	只用到了前一项，用一个临时变量即可
*/
func maxSubArray2(nums []int) int {
	f := nums[0]
	res := nums[0]
	for i := range nums {
		if i == 0 { // 初始化
			continue
		}
		f = max(f, 0) + nums[i]
		res = max(res, f)
	}
	return res
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func main() {
	nums := []int{-2, 1, -3, 4, -1, 2, 1, -5, 4}
	fmt.Println(maxSubArray1(nums))
	fmt.Println(maxSubArray2(nums))
}
